using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0064. 最小路径和")]
    public class No0064_SumNums : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(MinPathSum,
                new int[][] {
                    new int[] {1,3,1},
                    new int[] {1,5,1},
                    new int[] {4,2,1},
                }, 7);
        }

        public int MinPathSum(int[][] grid)
        {
            int len = grid[0].Length;
            int[] dp = new int[len];
            dp[0] = grid[0][0];
            for (int i = 1; i < len; i++)
            {
                dp[i] = dp[i - 1] + grid[0][i];
            }
            for (int i = 1; i < grid.Length; i++)
            {
                dp[0] = dp[0] + grid[i][0];
                for (int j = 1; j < len; j++)
                    dp[j] = Math.Min(dp[j - 1] + grid[i][j], dp[j] + grid[i][j]);
            }
            return dp[len - 1];
        }
    }
}
